// https://www.lintcode.com/problem/longest-common-subsequence/description

// - 描述
// 给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

// - 说明
// 最长公共子序列的定义：

// 最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
// https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
// The longest common subsequence (LCS) problem is the problem of 
// finding the longest subsequence common to all sequences in a set 
// of sequences (often just two sequences). 
// It differs from the longest common substring problem: unlike substrings, 
// subsequences are not required to occupy consecutive positions within the original sequences. 
// The longest common subsequence problem is a classic computer science problem, 
// the basis of data comparison programs such as the diff utility, 
// and has applications in bioinformatics. 
// It is also widely used by revision control systems such as Git 
// for reconciling multiple changes made to a revision-controlled collection of files.
// https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
// https://en.wikipedia.org/wiki/Diff

// - 样例
// 给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1

// 给出 "ABCD" 和 "EACB"，这个LCS是"AC"返回 2

// - 思路
// 和编辑距离差不多

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &A, string &B) {
        int la = A.length();
        int lb = B.length();
        if (!la || !lb)
        {
            return 0;
        }
        int **sub = new int* [la];
        for (int i = 0; i < la; i++)
        {
            sub[i] = new int[lb]; 
        }
        for (int i = 0; i < la; i++)
        {
            sub[i][0] = (A[i] == B[0]);
        }
        for (int i = 0; i < lb; i++)
        {
            sub[0][i] = (A[0] == B[i]);
        }
        for (int i = 1; i < la; i++)
        {
            for (int j = 1; j < lb; j++)
            {
                int tmp = sub[i - 1][j - 1];
                if (A[i] == B[j])
                {
                    tmp++;
                }
                sub[i][j] = max(max(sub[i][j - 1], sub[i - 1][j]), tmp);       
            }
        }
        return sub[la - 1][lb - 1];
    }
};